\section{Unit 5：大型矩阵与稀疏结构}

\begin{frame}{稀疏矩阵概述}
    \begin{block}{稀疏矩阵定义}
        非零元素比例很小的矩阵：
        \[ \text{稀疏度} = \frac{\text{非零元素数}}{\text{总元素数}} \ll 1 \]
        \begin{itemize}
            \item 典型稀疏度：$10^{-3}$到$10^{-6}$
            \item 存储效率：只存储非零元素和位置
            \item 计算效率：避免零元素运算
        \end{itemize}
    \end{block}
    
    \begin{block}{稀疏矩阵来源}
        \begin{itemize}
            \item 偏微分方程离散化
            \item 图论和网络问题
            \item 社交网络和推荐系统
            \item 有限元分析
            \item 电路模拟
        \end{itemize}
    \end{block}
    
    \begin{exampleblock}{稀疏性示例}
        \begin{itemize}
            \item 1000×1000矩阵，10000非零元素
            \item 稠密存储：1,000,000元素
            \item 稀疏存储：约30,000元素（位置+值）
            \item 存储节省：约97\%
        \end{itemize}
    \end{exampleblock}
\end{frame}

\begin{frame}{稀疏存储格式}
    \begin{block}{坐标格式（COO）}
        \begin{itemize}
            \item 存储：(行索引, 列索引, 值)三元组
            \item 简单但访问效率低
            \item 适用于矩阵构造
        \end{itemize}
    \end{block}
    
    \begin{block}{压缩稀疏行（CSR）}
        \begin{itemize}
            \item 三个数组：值，列索引，行指针
            \item 行访问高效
            \item 最常用的稀疏格式
        \end{itemize}
    \end{block}
    
    \begin{block}{压缩稀疏列（CSC）}
        \begin{itemize}
            \item CSR的转置版本
            \item 列访问高效
            \item 适用于列操作
        \end{itemize}
    \end{block}
    
    \begin{block}{其他格式}
        \begin{itemize}
            \item 对角线存储（DIA）
            \item 块稀疏格式（BSR）
            \item 天空线存储（SKY）
            \item 链表格式
        \end{itemize}
    \end{block}
\end{frame}

\begin{frame}{稀疏矩阵分解}
    \begin{block}{稀疏LU分解挑战}
        \begin{itemize}
            \item 填充（fill-in）：零元素变非零
            \item 填充控制：重排序减少填充
            \item 计算复杂度：$O(nnz(L) + nnz(U))$
        \end{itemize}
    \end{block}
    
    \begin{block}{填充减少技术}
        \begin{itemize}
            \item \textbf{最小度排序}：减少填充
            \item \textbf{嵌套剖分}：分治策略
            \item \textbf{Cuthill-McKee}：减少带宽
            \item \textbf{多重网格}：层次化方法
        \end{itemize}
    \end{block}
    
    \begin{block}{不完全分解}
        \begin{itemize}
            \item 允许一定填充的近似分解
            \item 用作预条件子
            \item ILU(0)：无填充不完全LU
            \item ILU(k)：允许k级填充
            \item ILUT：基于阈值的ILU
        \end{itemize}
    \end{block}
\end{frame}

\begin{frame}{稀疏图结构与矩阵}
    \begin{block}{图与矩阵的对应}
        \begin{itemize}
            \item 邻接矩阵：图的矩阵表示
            \item 非零模式：图的边结构
            \item 矩阵运算：图上的操作
        \end{itemize}
    \end{block}
    
    \begin{block}{重要图矩阵}
        \begin{itemize}
            \item \textbf{拉普拉斯矩阵}：$L = D - A$
            \item \textbf{标准化拉普拉斯}：$\mathcal{L} = D^{-1/2}LD^{-1/2}$
            \item \textbf{邻接矩阵}：$A$
            \item \textbf{度矩阵}：$D$（对角）
        \end{itemize}
    \end{block}
    
    \begin{block}{谱图理论}
        \begin{itemize}
            \item 特征值反映图的性质
            \item 代数连通度：$\lambda_2(L)$
            \item 图划分：基于特征向量
            \item 社区检测：谱聚类
        \end{itemize}
    \end{block}
    
    \begin{exampleblock}{图划分应用}
        \begin{itemize}
            \item 并行计算中的负载平衡
            \item VLSI电路布局
            \item 社交网络分析
            \item 图像分割
        \end{itemize}
    \end{exampleblock}
\end{frame}

\begin{frame}{稀疏Cholesky分解}
    \begin{block}{稀疏Cholesky特点}
        \begin{itemize}
            \item 适用于对称正定稀疏矩阵
            \item 计算$A = LL^T$
            \item 填充比LU分解少
            \item 数值稳定性好
        \end{itemize}
    \end{block}
    
    \begin{block}{稀疏Cholesky算法}
        \begin{enumerate}
            \item 符号分析：确定非零模式
            \item 数值分解：计算$L$的元素
            \item 三角求解：$Ly = b$, $L^Tx = y$
        \end{enumerate}
    \end{block}
    
    \begin{block}{填充控制策略}
        \begin{itemize}
            \item \textbf{AMD}：近似最小度排序
            \item \textbf{ND}：嵌套剖分
            \item \textbf{Metis}：多级图划分
            \item 这些策略可减少填充50-90\%
        \end{itemize}
    \end{block}
    
    \begin{block}{软件实现}
        \begin{itemize}
            \item CHOLMOD：SuiteSparse中的Cholesky分解
            \item PARDISO：并行直接求解器
            \item MUMPS：多前沿大规模求解器
            \item SuperLU：稀疏LU求解器
        \end{itemize}
    \end{block}
\end{frame}

\begin{frame}{应用：工程有限元分析}
    \begin{block}{有限元方法（FEM）}
        \begin{itemize}
            \item 偏微分方程数值解法
            \item 将连续问题离散化
            \item 产生大型稀疏线性系统
        \end{itemize}
    \end{block}
    
    \begin{block}{FEM矩阵特性}
        \begin{itemize}
            \item 对称正定（椭圆型问题）
            \item 带状或块状结构
            \item 条件数：$O(h^{-2})$，$h$为网格尺寸
            \item 需要高效的稀疏求解器
        \end{itemize}
    \end{block}
    
    \begin{block}{求解策略}
        \begin{itemize}
            \item \textbf{直接法}：Cholesky/LU分解，适用于中小问题
            \item \textbf{迭代法}：CG方法，适用于大规模问题
            \item \textbf{多重网格}：最优复杂度$O(n)$
            \item \textbf{域分解}：并行计算
        \end{itemize}
    \end{block}
    
    \begin{exampleblock}{典型FEM问题规模}
        \begin{itemize}
            \item 2D问题：$10^4-10^6$自由度
            \item 3D问题：$10^6-10^9$自由度
            \item 需要专门稀疏技术
            \item 并行计算必不可少
        \end{itemize}
    \end{exampleblock}
\end{frame}

\begin{frame}{应用：图计算与机器学习}
    \begin{block}{图计算应用}
        \begin{itemize}
            \item \textbf{PageRank}：网页排序
            \item \textbf{社区检测}：图划分
            \item \textbf{最短路径}：Dijkstra算法
            \item \textbf{最大流}：网络优化
        \end{itemize}
    \end{block}
    
    \begin{block}{机器学习中的稀疏矩阵}
        \begin{itemize}
            \item \textbf{推荐系统}：用户-物品矩阵
            \item \textbf{文本分析}：文档-词项矩阵
            \item \textbf{图神经网络}：邻接矩阵
            \item \textbf{稀疏编码}：字典学习
        \end{itemize}
    \end{block}
    
    \begin{block}{大规模机器学习}
        \begin{itemize}
            \item 数据矩阵通常稀疏
            \item 需要分布式稀疏计算
            \item 随机算法加速训练
            \item 增量学习处理流数据
        \end{itemize}
    \end{block}
    
    \begin{exampleblock}{实际应用规模}
        \begin{itemize}
            \item 社交网络：数十亿节点
            \item 推荐系统：百万用户×千万物品
            \item 需要特殊稀疏算法
            \item 分布式计算框架
        \end{itemize}
    \end{exampleblock}
\end{frame}

\begin{frame}{稀疏计算软件生态}
    \begin{block}{数值线性代数库}
        \begin{itemize}
            \item \textbf{SuiteSparse}：Tim Davis开发的C库
            \item \textbf{Eigen}：C++模板库
            \item \textbf{SPARSKIT}：Yousef Saad的Fortran库
            \item \textbf{PETSc}：并行求解器库
        \end{itemize}
    \end{block}
    
    \begin{block}{编程语言支持}
        \begin{itemize}
            \item \textbf{MATLAB}：内置稀疏矩阵类型
            \item \textbf{Python}：SciPy.sparse模块
            \item \textbf{Julia}：原生稀疏支持
            \item \textbf{R}：Matrix包
        \end{itemize}
    \end{block}
    
    \begin{block}{分布式计算框架}
        \begin{itemize}
            \item \textbf{Trilinos}：Sandia国家实验室
            \item \textbf{Hypre}：LLNL开发的预条件子库
            \item \textbf{SuperLU\_DIST}：分布式SuperLU
            \item \textbf{MUMPS}：并行多前沿求解器
        \end{itemize}
    \end{block}
\end{frame}

\begin{frame}{本章重点总结}
    \begin{block}{核心内容}
        \begin{itemize}
            \item 稀疏矩阵存储格式
            \item 稀疏分解与填充控制
            \item 图与矩阵的关系
            \item 稀疏Cholesky分解
        \end{itemize}
    \end{block}
    
    \begin{block}{技术要点}
        \begin{itemize}
            \item 填充对计算效率的影响
            \item 重排序减少填充
            \item 不完全分解作为预条件子
            \item 分布式稀疏计算
        \end{itemize}
    \end{block}
    
    \begin{block}{学习目标}
        \begin{itemize}
            \item 理解稀疏矩阵的特性
            \item 掌握稀疏存储格式
            \item 能够选择适当的稀疏算法
            \item 了解大规模稀疏计算挑战
        \end{itemize}
    \end{block}
\end{frame}